// @algorithm @lc id=416 lang=cpp 
// @title partition-equal-subset-sum


#define print(...)
// @test([1,5,11,5])=true
// @test([1,2,3,5])=false
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        print("nums=", nums, "\n")
        int n = nums.size();
        if(n<2) return false;
        int target = accumulate(nums.begin(), nums.end(), 0);
        print("sum:", target, "\n")
        if(target%2) return false;
        target /= 2;
        int maxElem = *max_element(nums.begin(), nums.end());
        print("maxElem:", maxElem, "\n")
        if(target<maxElem) return false;

        vector<bool> dp(target+1, false);
        dp[0] = dp[nums[0]] = true;
        for(int i=1; i<n; i++){
            vector<bool> np(target+1, false);
            np[0] = true;
            int j=1;
            for(; j<nums[i]; j++)
                np[j] = dp[j];
            for(; j<=target; j++)
                np[j] = dp[j] || dp[j-nums[i]];
            dp = np;
        }
        return dp[target];
    }
};